/**
 * Created by hongxiy on 2/29/2016.
 */
function HashMap() {
    var capacity = 16; //The default capacity(this could optimize the code when calculate the index of the table)
    var loadFactor = 0.75; //loadFactor
    var size = 0;
    var table = new Array(capacity); //define the table init


    /**
     * put the key-value to HashMap
     * @param key
     * @param value
     * @returns {boolean}
     */
    this.put = function (key, value) {
        if(capacity * 2 > (Math.MAX_VALUE)){
            throw Error("The HashMap size is too large, you can not put any Element");
        }
        if ((size / capacity) > loadFactor) {
            rehash(this);
        }
        var hashcode = hash(key);
        var index = indexOf(hashcode);  //find the index of table
        var current = table[index];
        if (current != undefined) {
            while (current != undefined) {
                var next = current.next;
                if (current.key == key && current.hash == hashcode) {
                    current.value = value;
                } else if (next == undefined) {
                    current.next = new Entry(hashcode, key, value);
                    size++;
                    return true;
                }
                current = next;
            }
        } else {
            table[index] = new Entry(hashcode, key, value);
            size++;
            return true;
        }
    };

    /**
     *
     * @param _this
     * @returns {boolean}
     */
    function rehash(_this) {
        var newTable = new Array();
        for (var i = 0; i < capacity; i++) {
            var current = table[i];
            while (current != undefined) {
                newTable.push(current);
                current = current.next;
            }
        }
        if (addCapacity()) {
            size = 0;
            table = new Array(capacity);
            for (var j = 0; j < newTable.length; j++) {
                var current = newTable[j];
                while (current != undefined) {
                    _this.put(current.key, current.value);
                    current = current.next;
                }
            }
            return true;
        } else {
            return false;
        }
    }

    /**
     * get the value from HashMap by key
     * @param key
     * @returns {*}
     */
    this.get = function (key) {
        var key = (typeof key == undefined) ? 0 : key.toString();
        var hashcode = hash(key);
        var index = indexOf(hashcode);
        var current = table[index];
        while (current != undefined) {
            if (current.key == key && current.hash == hashcode) {
                return current.value;
            }
            current = current.next;
        }
        return null;
    };

    /**
     * remove the key-value through the key, and return the delete Entry
     * @param key
     * @returns {*}
     */
    this.remove = function (key) {
        var key = (key == undefined) ? 0 : key.toString();
        var hashcode = hash(key);
        var index = indexOf(hashcode);
        var oldEntry = undefined;
        var prev = table[index];
        if (prev != undefined) {
            if (prev.key == key && prev.hash == hashcode) {
                oldEntry = prev;
                if (prev.next != undefined) {
                    table[index] = prev.next;
                } else {
                    table[index] = undefined;
                }
                size--;
                return oldEntry;
            }
            var current = prev.next;
            while (current != undefined) {
                if (current.key == key && current.hash == hashcode) {
                    oldEntry = current;
                    if (current.next != undefined) {
                        prev.next = current.next;
                        current = undefined;
                    } else {
                        current = undefined;
                    }
                    size--;
                    return oldEntry;
                }
                prev = current;
                current = current.next;
            }
        }
        return new Entry();
    };

    /**
     * check that whether there is the key
     * @param key
     * @returns {boolean}
     */
    this.containsKey = function (key) {
        var key = (key == undefined) ? 0 : key.toString();
        var hashcode = hash(key);
        var index = indexOf(hashcode);
        var current = table[index];
        //check the key
        while (current != undefined) {
            if (current.key == key && current.hash == hashcode) {
                return true;
            }
            current = current.next;
        }
        return false;
    };

    /**
     * check that whether there is the value
     * @param value
     * @returns {boolean}
     */
    this.containsValue = function(value){
        if(value == undefined){
            return false;
        }
        for(var i = 0; i < table.length; i++){
            var current = table[i];
            while(current != undefined){
                if(current.value == value){
                    return true;
                }
                current = current.next;
            }
        }
        return false;
    };

    /**
     * get the set of these keys
     * @returns {Array}
     */
    this.keySet = function(){
        var result = new Array();
        for(var i = 0; i < table.length; i++){
            var current = table[i];
            while(current != undefined){
                result.push(current.key);
                current = current.next;
            }
        }
        return result;
    };



    this.values = function(){
        var values = new Array();
        for(var i = 0; i < table.length; i++){
            var current = table[i];
            while(current != undefined){
                values.push(current.value);
                current = current.next;
            }
        }
        return values;
    };

    /**
     * return the number of Elements
     * @returns {number}
     */
    this.size = function () {
        return size;
    };

    /**
     * when the size/capacity>0.75 ,then make the capacity double
     * @returns {boolean}
     */
    function addCapacity() {
            capacity = capacity << 1;
    }

    /**
     * the hashcode of the key indexOf table
     */
    function indexOf(hashcode) {
        return hashcode ^ capacity;
    }

    /**
     * conculate the hashcode by key
     */
    function hash(key) {
        var seed = 31;
        var hashcode = 0;
        for (var i = 0; i < key.length; i++) {
            hashcode = (hashcode << 5) - hashcode + key.charCodeAt(i);
        }
        return hashcode;
    }

    /**
     *Define the hashEntry
     */
    function Entry(hash, key, value) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.prev = undefined;
        this.next = undefined;
    }
}

function test() {
    var map = new HashMap();
    var length = 5000000;

    for (var i = 0; i < length; i++) {
        map.put('t' + i, i);
    }
    var start = new Date().getTime();
    var end = new Date().getTime();
    console.log("hashmap 插入5千万条数据"+(end-start));

    var start0 = new Date().getTime();
    var arr = new Array(length);
    for (var i = 0; i < length; i++) {
        arr[i] = i;
    }
    var end0 = new Date().getTime();
    console.log("Array 插入5千万条数据"+(end0-start0));
}

test();
